#include<vector>
#include<algorithm>
using namespace std;

class Solution {

    int BFPTR(vector<int>&nums, int start, int end, int k) {
        int m_end = end;
        while (m_end- start >1) {
            int i = start;
            int j = start;
            while (i+5 <= m_end) {
                sort(nums.begin() + i, nums.begin() + i + 5);
                swap(nums[j++], nums[i + 2]);
                i += 5;
            }
            if (i < m_end) {
                sort(nums.begin() + i, nums.begin()+ m_end);
                swap(nums[j++], nums[i + (m_end - i) / 2]);
            }
            m_end = j;
        }
        int index=part(nums, start, end);
        if (index == k - 1)
            return nums[index];
        else if (index < k - 1)
            return BFPTR(nums, index + 1, end, k);
        else
            return BFPTR(nums, start, index, k);
    }


    int part(vector<int>&nums, int start, int end) {
        int left = start, right = end - 1;
        int priv = nums[left++];
        while (left <= right) {
            while (left <= right && nums[left] >= priv)++left;
            while (left <= right && nums[right] < priv)--right;
            if (left < right)
                swap(nums[left], nums[right]);
        }
        swap(nums[right], nums[start]);
        return right;

    }

    int findKthLargest(vector<int>&nums, int start, int end, int k) {
        int left = start, right = end - 1;
        int priv = nums[left++];
        while (left <= right) {
            while (left <= right && nums[left] >= priv)++left;
            while (left <= right && nums[right] < priv)--right;
            if (left < right)
                swap(nums[left], nums[right]);
        }
        swap(nums[right], nums[start]);
        if (right == k - 1)
            return nums[right];
        else if (right < k - 1)
            return findKthLargest(nums, right + 1, end, k);
        else
            return findKthLargest(nums, start, right, k);

    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        return BFPTR(nums, 0, nums.size(), k);

    }
};